- Quicksort
- Quicksort[dt. »Schnellsortierung«], ein Algorithmus zum Sortieren von Daten, der 1962 von dem britischen Informatiker Sir Antony (C. A. R., Tony) Hoarse (*Colombo, Sri Lanka 1934) erfunden wurde. Die Grundidee besteht darin, einen zu sortierenden Datensatz zunächst in zwei Teilmengen aufzuteilen, deren Elemente entweder alle kleiner oder alle größer als ein Vergleichselement sind, und dann diese Operation auf die Teilmengen ebenfalls anzuwenden. Dies wird so lange wiederholt, bis die Teilmengen aus zwei Elementen bestehen, welche direkt miteinander verglichen und »sortiert« werden können. Indem die Teilmengen mit den jeweils kleineren Elementen durch geeignete Indexvariablen als »kleiner« markiert werden (bildlich »nach links« gestellt werden), erhält man nach einer vollständigen Zerlegung in Zweiermengen bzw. einzelne Zahlen automatisch die richtige Sortierung.Für eine schnelle Sortierung ist es wesentlich, auf welche Weise das Vergleichselement bestimmt wird. Es muss - wie leicht einzusehen ist - immer zu möglichst gleich großen Teilmengen führen und andererseits schnell zu ermitteln sein. Dies erreicht man z. B. durch Wahl des arithmetischen Mittels des ersten und letzten Elements der aufzuteilenden Datenmenge.Die durchschnittliche Zeit (bzw. Anzahl der Rechenschritte), die der Algorithmus für das Sortieren von n Daten benötigt, beträgt etwa 3 · n· log n, damit ist Quicksort das schnellste bekannte Sortierverfahren. Allerdings steigt diese Zahl im »worst Case«, d. h. im ungünstigsten Fall, wenn der gewählte Vergleichswert immer das kleinste oder größte Element einer Teilmenge ist, auf mehr als n2 an.Da andere Sortierverfahren ein besseres Worst-Case-Verhalten zeigen, wird bei Sortieraufgaben mit großen Datensätzen, bei denen eine gewisse Maximaldauer auf keinen Fall überschritten werden darf, auf solche Methoden zurückgegriffen, etwa auf Heapsort.
Universal-Lexikon. 2012.
